/*
 * @lc app=leetcode id=234 lang=java
 *
 * [234] Palindrome Linked List
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
        public boolean isPalindrome(ListNode head) {
        //write code here
        if (head == null && head.next == null) {
            return true;
        }
        ListNode fast = head;
        ListNode slow = head;

        while(fast!=null&&fast.next!=null)
        {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode cur = slow.next;
        slow.next = null;
        //中间节点slow
        while(cur!=null)
        {
            ListNode curN = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curN;
        }
        while(slow!=null)
        {
            if (slow.val != head.val) {
                return false;
            } else {
                slow = slow.next;
                fast = fast.next;
            }
        }
        return true;
    }
}
// @lc code=end

